package com.antsing.algorithms.sort;

/**
 * 各种排序算法集合类
 */
public final class Sort {
    /**
     * 插入排序:产生有小到大的序列
     *  #从0和1位置开始比较，从而产生0到1位置有序的序列
     *  #从后面无序的序列中取首个数值作为比较对象跟有序序列进行挨个比较，
     * @param arr
     * @param <T>
     */
    public static <T extends Comparable<? super T>> void insertionSort(T arr[]){
        int compareIdx;
        for(int i = 1;i<arr.length;i++){
            T temp = arr[i];
            for(compareIdx = i;compareIdx > 0 && temp.compareTo(arr[compareIdx - 1]) < 0;compareIdx--)
                arr[compareIdx] = arr[compareIdx -1];
            arr[compareIdx] = temp;
        }
    }

    public static void main(String[] args) {
         Integer arr[] = {9,5,3,6,1,2,4};
        Sort.insertionSort(arr);
        for(int i=0;i<arr.length;i++){
            System.out.printf(" %d ",arr[i]);
        }
    }
}
